package Leetcode第二期;

import java.util.LinkedList;

/**
 * @author : K k
 * @date : 15:40 2020/10/18
 * 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
 *
 * 例如，从根到叶子节点路径 1->2->3 代表数字 123。
 *
 * 计算从根到叶子节点生成的所有数字之和。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例 1:
 *
 * 输入: [1,2,3]
 *     1
 *    / \
 *   2   3
 * 输出: 25
 * 解释:
 * 从根到叶子节点路径 1->2 代表数字 12.
 * 从根到叶子节点路径 1->3 代表数字 13.
 * 因此，数字总和 = 12 + 13 = 25.
 */
public class 求根到叶子节点数字之和_129 {
    int sum=0;
    //DFS
    public int sumNumbers(TreeNode root) {
        dfs(root,0);
        return sum;
    }
    //前序遍历
    private void dfs(TreeNode root,long count) {
        if (root==null){
            //单节点为空
            return;
        }

        if (root.left==null && root.right==null){
            //到达叶子节点
            count=count*10+root.val;
            sum+=count;
            return;
        }
        count=count*10+root.val;
        dfs(root.left,count);
        dfs(root.right,count);
        count=(count-root.val)/10;
    }
}
